# -!- coding: utf-8 -!-
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
#作者：cacho_37967865
#博客：https://blog.csdn.net/sinat_37967865
#文件：deal_sudoku.py
#日期：2024-03-09
#备注：数独填空:回溯算法
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''


def deal_su_do():
    su_du = []
    for i in range(9):
        temp = []
        for j in range(9):
            temp.append(0)
        su_du.append(temp)
    su_du[0][0] =9
    su_du[0][1] = 4
    su_du[0][3] = 8
    su_du[0][6] = 6
    su_du[0][8] = 2
    su_du[1][2] = 3
    su_du[1][6] = 5
    su_du[1][7] = 8
    su_du[2][1] = 2
    su_du[2][2] = 1
    su_du[2][5] = 3
    su_du[3][3] = 3
    su_du[3][5] = 6
    su_du[4][2] = 4
    su_du[4][3] = 2
    su_du[4][7] = 7
    su_du[5][3] = 7
    su_du[5][5] = 5
    su_du[6][1] = 3
    su_du[6][3] = 4
    su_du[6][7] = 5
    su_du[7][1] = 8
    su_du[7][6] = 3
    su_du[8][0] = 5
    su_du[8][2] = 6
    su_du[8][8] = 7
    #print (su_du)
    return su_du

# 判断是否解题成功（棋盘无0）
def findEmpty(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0 :
                return row,col
    return None

# 判断某个输入是否有效（3层判断）
def isValid(board, num, pos):
    row, col = pos
    # 同一行的任何子单元格cell都不应包含该数字
    for j in range(9):
        if board[row][j] == num:
            return False
    # 同一列的任何子单元格cell都不应包含该数字
    for i in range(9):
        if board[i][col] == num:
            return False
    # 该子单元格cell所在的block不应该包含该数字
    rowBlockStart = 3* (row // 3)
    colBlockStart = 3* (col // 3)

    rowBlockEnd = rowBlockStart + 3
    colBlockEnd = colBlockStart + 3
    for i in range(rowBlockStart, rowBlockEnd):
        for j in range(colBlockStart, colBlockEnd):
            if board[i][j] == num:
                return False
    return True

def deal_sudu():
    board = deal_su_do() # 数独初始化
    def solve(board):
        pos = findEmpty(board)
        if not pos:
            print("无空格，跳出！")
            return True
        else:
            row, col = pos
        for i in range(1,10):
            if isValid(board, i, pos):
                board[row][col] = i # 填充进去
                # 找到一个有效的数字，此时递归调用solve() 函数并猜测下一个空的子单元格cell
                if solve(board):
                    return True
                # 如果数字1-9均无效，则将子单元格cell的值重置为 0，并继续迭代以查找下一个有效数字
                board[row][col] = 0
        return False
    # 回溯算法入口
    solve(board)
    return board

if __name__ == '__main__':
    print(deal_sudu())